换零钞
题目 换零钞
思路分析
起初考虑dfs枚举所有可能 但效率太低 半天出不来结果
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int res = 300; // 用来记录最小的钞票数，初始设为一个比较大的值
void dfs(int sum, int cnt1, int cnt2, int cnt5) {
if(sum > 200) return; // 如果累计金额超过200，停止递归
if(cnt1 > 0 && cnt2 > 0 && cnt5 > 0 && sum == 200) { // 确保每种面额至少有1张
if(cnt2 == 10 * cnt1) { // 检查是否满足2元是1元的10倍
res = min(res, cnt1 + cnt2 + cnt5);
}
return;
}
// 继续进行递归搜索，考虑添加1元、2元和5元
dfs(sum + 1, cnt1 + 1, cnt2, cnt5);
dfs(sum + 2, cnt1, cnt2 + 1, cnt5);
dfs(sum + 5, cnt1, cnt2, cnt5 + 1);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
dfs(0, 0, 0, 0);
cout << res << endl;
return 0;
}
改进为直接迭代
- 直接迭代 1 元和 2 元的数量，计算出必须的 5 元数量来达到 200 元。
- 根据 2 元的张数是 1 元的 10 倍这一条件进行迭代
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int INF=300;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int res = INF;
// cnt1代表1元的数量，cnt2代表2元的数量，cnt5代表5元的数量
// 由于2元的数量是1元的10倍，因此cnt1和cnt2可以直接通过cnt1计算得到
for (int cnt1 = 1; cnt1 <= 200; ++cnt1) {
int cnt2 = 10 * cnt1; // 2元的数量是1元的10倍
if (cnt2 > 200) break; // 如果2元的总额已超过200元，则停止循环
int remaining = 200 - cnt1 - 2 * cnt2; // 计算剩余金额
if (remaining < 0) continue; // 如果剩余金额为负，则当前组合无效
if (remaining % 5 == 0) { // 剩余金额必须能被5整除才合理
int cnt5 = remaining / 5; // 计算5元的数量
res = min(res, cnt1 + cnt2 + cnt5); // 更新最小钞票数量
}
}
if (res == INF)
cout << "Can't found." << endl;
else
cout << res << endl;
return 0;
}
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int INF=300;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int res = INF;
// cnt1代表1元的数量，cnt2代表2元的数量，cnt5代表5元的数量
// 由于2元的数量是1元的10倍，因此cnt1和cnt2可以直接通过cnt1计算得到
for (int cnt1 = 1; cnt1 <= 200; ++cnt1) {
int cnt2 = 10 * cnt1; // 2元的数量是1元的10倍
if (cnt2 > 200) break; // 如果2元的总额已超过200元，则停止循环
int remaining = 200 - cnt1 - 2 * cnt2; // 计算剩余金额
if (remaining < 0) continue; // 如果剩余金额为负，则当前组合无效
if (remaining % 5 == 0) { // 剩余金额必须能被5整除才合理
int cnt5 = remaining / 5; // 计算5元的数量
res = min(res, cnt1 + cnt2 + cnt5); // 更新最小钞票数量
}
}
if (res == INF)
cout << "Can't found." << endl;
else
cout << res << endl;
return 0;
}
同类题型
视频讲解
⬅️ 第九届蓝桥杯大赛软件赛决赛C/C++ 大学 B 组 🏠 00-冲刺国赛 ➡️ 激光样式
💬 评论